package Algorithm.Othes;

import java.util.HashMap;
import java.util.Map;

public class Leetcode1995_统计特殊四元组 {
    /**
     * O(N**3)
     */
    class Solution {
        public int countQuadruplets(int[] nums) {
            Map<Integer, Integer> map = new HashMap();
            int ans = 0;

            for(int c = nums.length-2; c>=2;c--){
                map.put(nums[c+1], map.getOrDefault(nums[c+1], 0) + 1);

                for(int b = c - 1; b >= 1; b--){
                    for(int a = b - 1; a >= 0 ; a--){
                        int sum = nums[c] + nums[b] + nums[a];

                        ans += map.getOrDefault(sum, 0);
                    }
                }
            }

            return ans;
        }
    }

    /**
     * O(n**2)
     */
    class Solution2 {
        public int countQuadruplets(int[] nums) {
            int n = nums.length;
            int ans = 0;
            Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
            for (int b = n - 3; b >= 1; --b) {
                for (int d = b + 2; d < n; ++d) {
                    cnt.put(nums[d] - nums[b + 1], cnt.getOrDefault(nums[d] - nums[b + 1], 0) + 1);
                }
                for (int a = 0; a < b; ++a) {
                    ans += cnt.getOrDefault(nums[a] + nums[b], 0);
                }
            }
            return ans;
        }
    }

}
